A wireless ad-hoc network, also referred to as a mobile ad-hoc network (MANET), is known to comprise a set of nodes connected by wireless links. Typical examples of ad-hoc networks are wireless sensor networks, where the nodes are sensors that gather environmental data and send the information to computational nodes for further processing, or to base stations for relay to a wired network. Such networks may be deployed, for example, in hazardous locations such as in disaster areas to aid rescue efforts, in areas for mineral or oil prospecting, and in battlefields for defense applications.
The topology of an ad-hoc network is dynamic since nodes are typically free to move randomly and organize themselves arbitrarily. Therefore, the topology may be determined by the current geographic location of the nodes and other environmental conditions, and the characteristics of the radio transceivers that the nodes possess. The topology may therefore be represented as an arbitrary graph with “nodes” of the graph representing nodes in the network and “edges” of the graph representing links between nodes.
The nodes in an ad-hoc network typically attempt to communicate amongst each other by relaying packets. However, due to the limited transmission range that is characteristic of nodes in an ad-hoc network, multiple network “hops” are typically needed for one node to exchange data with another node across the network. The problem is to design effective routing protocols to meet a variety of performance objectives given such a communications environment.
Most existing routing protocols for wireless ad-hoc networks concentrate on finding and maintaining routes in the face of changing topology caused by mobility or other environmental changes. Typical protocols use shortest path methodologies based on hop count, geographic distance, or transmission power. The first two are important in minimizing delay and maximizing throughput. The third objective is peculiar to wireless ad-hoc networks, and is important because typically the nodes involved have a limited power supply, and radio communication consumes a large fraction of this supply.
To address this issue, several power-aware routing and topology control methodologies have been developed. In most of these methodologies, the aim is to minimize the energy consumed per packet in order to deliver it to the destination. The typical approach is to use a distributed shortest path methodology in which the edge costs are related to the power required to transmit a packet between the two nodes involved. The problem with this technique is that nodes on the minitnum-energy path are quickly drained of power, affecting the network connectivity when they fail.
Some of the more sophisticated routing methodologies associate a cost with routing through a node with low power reserves. But this remains, at best, a heuristic solution.
A formulation using linear programming has been proposed which attempts to capture the issue of power consumption more precisely, see J. H. Chang et al., “Routing for Maximum System Lifetime in Wireless Ad-hoc Networks,” Proceedings of 37th Annual Allerton Conference on Communication, Control and Computing, September 1999; and J. H. Chang et al., “Energy Conserving Routing in Wireless Ad-hoc Networks” Proceedings of IEEE INFOCOM, pp. 22-31, March 2000, the disclosures of which are incorporated by reference herein. The idea is to make the goal of routing the maximization of the “network lifetime.” As is known, the network lifetime is the time period in which the network operates without a node failure. This maximization approach utilizes a heuristic methodology to solve the linear program approximately. However, such a heuristic approach can perform arbitrarily poorly in worst case situations.
Further, a centralized methodology to determine the maximum lifetime has been proposed in J. H. Chang et al., “Fast Approximation Algorithms for Maximum Lifetime Routing in Wireless Ad-hoc Networks,” Lecture Notes in Computer Science: Networking 2000, vol. 1815, pp. 702-713, May 2000, the disclosure of which is incorporated by reference herein. Such centralized methodology is based on the Garg-Koenemann methodology for multicommodity flow, as described in N. Garg et al., “Faster and Simpler Algorithm for Multicommodity Flow and Other Fractional Packing Problems, Proceedings of 39th Annual Symposium on Foundations of Computer Science, pp. 300-309, November 1998, the disclosure of which is incorporated by reference herein. However, this approach does not solve all of the performance deficiencies associated with the above linear programming approach.
Accordingly, a need still exists for effective routing techniques that meet performance objectives associated with an ad-hoc network environment and the like.